// https://leetcode.cn/problems/decode-ways/

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;


class Solution {
public:
    // dfs 的方式会超时
    int numDecodings(string s) {
        int len = s.size();
        int sum = 0;
        if (s[0] == '0') return 0;
        while (len > 0 && s[len - 1] == '0') {
            len--;
        }
        if (len <= 1) {
            return 1;
        }

        // index 代表的是开头的字母，开头的字母是不能以0开头的
        auto dfs = [&](auto &&me, int index) {
            if (index >= len - 1) {
                sum++;
                return;
            }
            if (s[index] == '0') return;
            if (index < len - 1) {
                if (s[index] == '1') {
                    if (s[index + 1] == '0') {
                        me(me, index + 2);
                    } else {
                        me(me, index + 1);
                        me(me, index + 2);
                    }
                } else if (s[index] == '2') {
                    if (s[index + 1] == '0' || s[index + 1] >= '7') {
                        me(me, index + 2);
                    } else {
                        me(me, index + 1);
                        me(me, index + 2);
                    }
                } else {
                    me(me, index + 1);
                }
            } else {
                me(me, index + 1);
            }
        };
        dfs(dfs, 0);
        return sum;
    }

    // 动态规划
    int numDecodings1(string s) {
        int len = s.size();
        if (s[0] == '0') return 0;
        vector<int> dp(len + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i < len; i++) {
            if (s[i] == '0') {
                if (s[i - 1] == '1' || s[i - 1] == '2') {
                    dp[i + 1] = dp[i - 1];
                } else {
                    return 0;
                }
            } else {
                if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
                    dp[i + 1] = dp[i] + dp[i - 1];
                } else {
                    dp[i + 1] = dp[i];
                }
            }
        }
        return dp[len];
    }
};

int main() {
    Solution so;
    string s = "12"; // 正确的应该是2
//    string s = "226"; // 正确/的应该是3
//    string s = "2101"; // 正确的应该是1
//    string s = "2611055971756562"; // 正确的应该是4
    /*
     2 6 1 10 5  5 5 9 7 17  5 6 5 6 2
     26 1 10 5  5 9 7 17  5 6 5 6 2
     * */
    cout << s << endl;
    int res = so.numDecodings(s);
    cout << "res:" << res << endl;
    return 0;
}